import java.util.HashMap;
import java.util.Map;

/**
 * 面试题18-2：删除排序链表中重复的节点
 * <p>
 * 如：1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 操作后变为：1 -> 2 -> 5
 */
public class Offer_18_II {
    /**
     * 方法二：一次遍历
     * <p>
     * 方法一没有用到题目中的「排序」特性。因为排序，重复元素的位置是连续的。
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }

        // 虚拟头节点
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;

        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                // 如果当前 cur.next 与 cur.next.next 对应的元素相同，
                // 就需要将 cur.next 以及所有后面拥有相同元素值的链表节点全部删除
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                // 否则正常遍历链表
                cur = cur.next;
            }
        }
        return dummyHead.next;
    }

    /**
     * 方法一：哈希表 + 两次遍历
     * <p>
     * 用哈希表记录每个元素出现的次数，删除多次出现的元素即可
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public ListNode deleteDuplicates1(ListNode head) {
        if (head == null) {
            return null;
        }

        // 虚拟头节点
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;

        // 记录每个数字出现的次数，key 为数字，value 为该数字出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        // 第一次遍历链表，记录每个数字出现的次数
        while (cur.next != null) {
            int x = cur.next.val;
            map.put(x, map.getOrDefault(x, 0) + 1);
            cur = cur.next;
        }

        // 回到起点
        cur = dummyHead;

        // 第二次遍历链表，删除重复数字
        while (cur.next != null) {
            int x = cur.next.val;
            if (map.get(x) > 1) {
                // 如果该数字在链表中多次出现，则将其删除
                cur.next = cur.next.next;
            } else {
                // 否则正常遍历链表
                cur = cur.next;
            }
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        Offer_18_II solution = new Offer_18_II();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(4);
        head.next.next.next.next.next = new ListNode(4);
        head.next.next.next.next.next.next = new ListNode(5);
        solution.printListNode(head);

        ListNode ans = solution.deleteDuplicates(head);
        solution.printListNode(ans);
    }

    public void printListNode(ListNode node) {
        ListNode cur = node;
        System.out.print("[");
        while (cur != null) {
            System.out.print(cur.val + " -> ");
            cur = cur.next;
        }
        System.out.println("null]");
    }
}
